package binarysearch.寻找两个正序数组的中位数;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        int midIndex = n / 2;
        int count = -1;
        int midValue = 0;
        int preValue = 0;
        int i1 = 0;
        int i2 = 0;
        while (i1 < nums1.length || i2 < nums2.length) {
            if (i1 < nums1.length && i2 < nums2.length) {
                count++;
                if (nums1[i1] < nums2[i2]) {
                    preValue = midValue;
                    midValue = nums1[i1];
                    i1++;
                } else {
                    preValue = midValue;
                    midValue = nums2[i2];
                    i2++;
                }
            } else if (i1 < nums1.length) {
                count++;
                preValue = midValue;
                midValue = nums1[i1];
                i1++;
            } else {
                count++;
                preValue = midValue;
                midValue = nums2[i2];
                i2++;
            }
            if (midIndex == count) {
                if (n % 2 == 0) {
                    return (preValue + midValue) / 2.0;
                } else {
                    return Double.valueOf(midValue);
                }
            }
        }
        return midValue;
    }

    public static void main(String[] args) {
        Solution so = new Solution();
        System.out.println(so.findMedianSortedArrays(new int[]{-101, 3}, new int[]{-2,4}));
    }
}
